<style>
    .cell {
        display: inline-block;
        line-height: 7px;
        width: 6px;
        height: 6px;
        background-color: gray;
        border-bottom: solid 1px white;
        border-right: solid 1px white;
        vertical-align: top;
    }

    #container {
        width: 701px;
    }
</style>
<div id="container"></div>

<!--使用 JSON.stringify() 方法将 JavaScript 对象转换为字符串。-->
<!--使用 local Storage 创建一个本地存储的 name/value 对，name="lastname" value="Smith", 然后检索 "lastname" 的值，并插入到 id="result" 的元素上-->
<button onclick="localStorage['map']= JSON.stringify(map)"> save </button>
<p id="count">从起点到终点总共需要 步</p>
<script>
    //具有排序功能的数据结构
    class Sorted {
        constructor(data) {
            this.data = data.slice();
        }
        //取出其中最小元素
        take() {
            if (!this.data.length) {
                return;
            }

            if (this.data.length === 1) {
                return this.data.pop();
            }

            let min = this.data[0];
            let minIndex = 0;

            for (let i = 1; i < this.data.length; i++) {
                if (this.data[i][4] - min[4] < 0) {
                    min = this.data[i];
                    minIndex = i;
                }
            }

            this.data[minIndex] = this.data[this.data.length - 1];
            this.data.pop();
            console.log(this.data)
            return min;
        }
        //放入一个元素
        give(v) {
            this.data.push(v);
        }
        //返回元素个数
        number() {
            return this.data.length;
        }
        //查询数组中是否已存在某个元素
        has(v) {
            //坑！不用查询完整信息，只用对比点的坐标即可
            const have = this.data.find(element => element[0] == v[0] && element[1] == v[1]);
            return have != undefined;
            // return this.data.includes(v);
        }
    }
    //JSON.parse() 方法用来解析JSON字符串，构造由字符串描述的JavaScript值或对象。
    let map = localStorage["map"] ? JSON.parse(localStorage["map"]) : Array(10000).fill(0);
    let container = document.getElementById("container")

    let mousedone = false;
    let clear = false;

    //绘制地图
    for (let x = 0; x < 100; x++) {
        for (let y = 0; y < 100; y++) {
            let cell = document.createElement("div");
            cell.classList.add("cell");
            //0代表没墙，1代表有墙，颜色区分
            if (map[100 * x + y] == 1) {
                cell.style.backgroundColor = "black";
            }
            //编辑地图
            cell.addEventListener("mousemove", () => {
                if (mousedone) {
                    if (clear) {
                        cell.style.backgroundColor = "";
                        map[100 * x + y] = 0;
                    } else {
                        cell.style.backgroundColor = "black";
                        map[100 * x + y] = 1;
                    }
                }
            })
            container.appendChild(cell);
        }
    }
    //e简单来说就是指向了当前发生的事件
    document.addEventListener("mousedown", e => {
        mousedone = true;
        //event.which也将正常化的按钮按下(mousedown 和 mouseupevents)，左键报告1，中间键报告2，右键报告3
        clear = (e.which === 3)
    })
    document.addEventListener("mouseup", () => mousedone = false);
    document.addEventListener("contextmenu", e => e.preventDefault());

    function sleep(t) {
        return new Promise(function (resolve, reject) {
            setTimeout(resolve, t);
        });
    }

    //寻路,利用启发式搜索A*算法，async 函数返回的是一个 Promise 对象
    async function findPath(map, start, end) {

        var openlist = new Sorted([start]); //开启列表
        var closelist = new Map(); //关闭列表

        //openlist入队,x,y分别为新探索节点坐标，px,py分别为新探索节点的父节点坐标，startdis为新探索节点的父节点到起点的距离
        async function insert(x, y, px, py, startdis) {
            //1.计算寻路消耗，dis代表寻路消耗，start代表该点距离起点的距离
            let [dis, newstartdis] = distance(x, y, px, py, startdis);
            //2.判断是否遇到边，不添加
            if (x < 0 || x >= 100 || y < 0 || y >= 100) {
                return;
            }
            //3.判断是否遇到墙或者已加入openlist,closelist，则不用再次管它
            console.log(openlist.has([x, y, px, py, dis, newstartdis]))
            if (map[x * 100 + y] || openlist.has([x, y, px, py, dis, newstartdis]) || closelist.has(x * 100 + y))
                return;

            container.children[x * 100 + y].style.backgroundColor = "lightgreen";
            await sleep(5);

            //4.保存该节点相关信息到openlist
            openlist.give([x, y, px, py, dis, newstartdis]);

            return;
        }

        //计算寻路消耗=该节点到父节点的距离+父节点到起点的距离+该节点到终点的距离
        function distance(x, y, px, py, startdis) {
            startdis = Math.sqrt((x - px) ** 2 + (y - py) ** 2) + startdis;
            return [Math.sqrt((x - end[0]) ** 2 + (y - end[1]) ** 2) + startdis, startdis];
        }

        //每次从openlist找到寻路消耗最小的点，进而找到最佳到达路径，并绘制出来
        while (openlist.number()) {
            //1.从openlist出队，选取优先级最高的节点
            let [x, y, px, py, dis, startdis] = openlist.take();

            //2.如果是最终节点，则绘制路径，计算总步数
            if (x === end[0] && y === end[1]) {
                closelist.set(x * 100 + y, [px, py]);

                let count = 1; //记录总步数
                let path = []; //记录路径坐标
                path.push([x, y]);
                container.children[x * 100 + y].style.backgroundColor = "purple";

                while (x != start[0] || y != start[1]) {
                    [x, y] = closelist.get(x * 100 + y); //找到父节点坐标
                    path.push([x, y]); //节点加入路径
                    await sleep(5);
                    container.children[x * 100 + y].style.backgroundColor = "purple";
                    count++;
                }

                document.getElementById("count").innerHTML = "从起点到终点总共需要" + count + "步";
                console.log(path);
                return path;
            }
            //3.如果不是最终节点，放入closelist,并记录父节点;await 可以用于等待一个 async 函数的返回值——这也可以说是 await 在等 async 函数，但要清楚，它等的实际是一个返回值。
            closelist.set(x * 100 + y, [px, py]);

            //4.遍历该节点的临近节点
            await insert(x + 1, y, x, y, startdis);
            await insert(x - 1, y, x, y, startdis);
            await insert(x, y + 1, x, y, startdis);
            await insert(x, y - 1, x, y, startdis);

            await insert(x + 1, y + 1, x, y, startdis);
            await insert(x - 1, y - 1, x, y, startdis);
            await insert(x - 1, y + 1, x, y, startdis);
            await insert(x + 1, y - 1, x, y, startdis);
        }
        return null;
    }

    findPath(map, [0, 0, 0, 0, 0, 0], [99, 99]);

</script>